Search for: All records

We consider the placement, delivery promise, and fulfillment decisions of an online retailer. We have a set of products with given numbers of units to be placed at capacitated fulfillment centers. Once we make the placement decisions, we face demands for the products arriving from different demand regions randomly over time. In response to each demand, we pick a delivery promise to offer, which determines the probability that the demand converts into sales as well as choose a fulfillment center to use to serve the demand. Our goal is to decide where to place the units at the beginning of the selling horizon and to find a policy to make delivery promise and fulfillment decisions over the selling horizon so that we maximize the total expected profit. We give an approximation strategy to obtain solutions with performance guarantees for this joint placement, delivery promise, and fulfillment problem. In our approximation strategy, we construct a bounding function that upper bounds the total expected profit from the delivery promise and fulfillment policy when viewed as a function of the placement decisions. To make the placement decisions, we maximize the bounding function subject to the capacity constraints at the fulfillment centers. To make the delivery promise and fulfillment decisions, we construct a policy that obtains a constant fraction of the bounding function. Using our approximation strategy with appropriate bounding functions, we obtain a solution with a constant factor performance guarantee, but if the size of the system, measured by the numbers of units that we need to place and capacities of the fulfillment centers, is large, then we get an asymptotically optimal solution. We compare our approximation strategy with approaches that ignore the interactions between the placement, delivery promise, and fulfillment decisions as well as heuristics that are based on Lagrangian relaxation, demonstrating that our approximation strategy compares quite favorably. 

Jointly Making Inventory Stocking and Assortment Offering Decisions Making the product assortment offer decisions for a customer requires keeping a balance between offering an assortment that will satisfy the current customer and reserving the products with scarce inventories for the customers who will arrive in the future. Therefore, whereas the assortment offer decisions should depend on the current inventories of the products, the stocking decisions should anticipate how the offered assortments will deplete the inventories, thereby creating a natural interaction between inventory stocking and assortment offer decisions. In “Coordinated Inventory Stocking and Assortment Customization,” Bai, El Housni, Rusmevichientong, and Topaloglu develop models that jointly make the assortment offer and inventory stocking decisions. Their models allocate the limited stocking capacity to the inventories for different products, while taking into consideration the assortment offer decisions that will be made for the customers arriving over a selling horizon. 

We develop a variant of the multinomial logit model with impatient customers and study assortment optimization and pricing problems under this choice model. In our choice model, a customer incrementally views the assortment of available products in multiple stages. The patience level of a customer determines the maximum number of stages in which the customer is willing to view the assortments of products. In each stage, if the product with the largest utility provides larger utility than a minimum acceptable utility, which we refer to as the utility of the outside option, then the customer purchases that product right away. Otherwise, the customer views the assortment of products in the next stage as long as the customer’s patience level allows the customer to do so. Under the assumption that the utilities have the Gumbel distribution and are independent, we give a closed-form expression for the choice probabilities. For the assortment-optimization problem, we develop a polynomial-time algorithm to find the revenue-maximizing sequence of assortments to offer. For the pricing problem, we show that, if the sequence of offered assortments is fixed, then we can solve a convex program to find the revenue-maximizing prices, with which the decision variables are the probabilities that a customer reaches different stages. We build on this result to give a 0.878-approximation algorithm when both the sequence of assortments and the prices are decision variables. We consider the assortment-optimization problem when each product occupies some space and there is a constraint on the total space consumption of the offered products. We give a fully polynomial-time approximation scheme for this constrained problem. We use a data set from Expedia to demonstrate that incorporating patience levels, as in our model, can improve purchase predictions. We also check the practical performance of our approximation schemes in terms of both the quality of solutions and the computation times. 

We examine the revenue–utility assortment optimization problem with the goal of finding an assortment that maximizes a linear combination of the expected revenue of the firm and the expected utility of the customer. This criterion captures the trade-off between the firm-centric objective of maximizing the expected revenue and the customer-centric objective of maximizing the expected utility. The customers choose according to the multinomial logit model, and there is a constraint on the offered assortments characterized by a totally unimodular matrix. We show that we can solve the revenue–utility assortment optimization problem by finding the assortment that maximizes only the expected revenue after adjusting the revenue of each product by the same constant. Finding the appropriate revenue adjustment requires solving a nonconvex optimization problem. We give a parametric linear program to generate a collection of candidate assortments that is guaranteed to include an optimal solution to the revenue–utility assortment optimization problem. This collection of candidate assortments also allows us to construct an efficient frontier that shows the optimal expected revenue–utility pairs as we vary the weights in the objective function. Moreover, we develop an approximation scheme that limits the number of candidate assortments while ensuring a prespecified solution quality. Finally, we discuss practical assortment optimization problems that involve totally unimodular constraints. In our computational experiments, we demonstrate that we can obtain significant improvements in the expected utility without incurring a significant loss in the expected revenue. This paper was accepted by Omar Besbes, revenue management and market analytics. 

We consider dynamic assortment problems with reusable products, in which each arriving customer chooses a product within an offered assortment, uses the product for a random duration of time, and returns the product back to the firm to be used by other customers. The goal is to find a policy for deciding on the assortment to offer to each customer so that the total expected revenue over a finite selling horizon is maximized. The dynamic-programming formulation of this problem requires a high-dimensional state variable that keeps track of the on-hand product inventories, as well as the products that are currently in use. We present a tractable approach to compute a policy that is guaranteed to obtain at least 50% of the optimal total expected revenue. This policy is based on constructing linear approximations to the optimal value functions. When the usage duration is infinite or follows a negative binomial distribution, we also show how to efficiently perform rollout on a simple static policy. Performing rollout corresponds to using separable and nonlinear value function approximations. The resulting policy is also guaranteed to obtain at least 50% of the optimal total expected revenue. The special case of our model with infinite usage durations captures the case where the customers purchase the products outright without returning them at all. Under infinite usage durations, we give a variant of our rollout approach whose total expected revenue differs from the optimal by a factor that approaches 1 with rate cubic-root of Cmin, where Cmin is the smallest inventory of a product. We provide computational experiments based on simulated data for dynamic assortment management, as well as real parking transaction data for the city of Seattle. Our computational experiments demonstrate that the practical performance of our policies is substantially better than their performance guarantees and that performing rollout yields noticeable improvements. 

We provide an approximation algorithm for network revenue management problems. In our approximation algorithm, we construct an approximate policy using value function approximations that are expressed as linear combinations of basis functions. We use a backward recursion to compute the coefficients of the basis functions in the linear combinations. If each product uses at most L resources, then the total expected revenue obtained by our approximate policy is at least [Formula: see text] of the optimal total expected revenue. In many network revenue management settings, although the number of resources and products can become large, the number of resources used by a product remains bounded. In this case, our approximate policy provides a constant-factor performance guarantee. Our approximate policy can handle nonstationarities in the customer arrival process. To our knowledge, our approximate policy is the first approximation algorithm for network revenue management problems under nonstationary arrivals. Our approach can incorporate the customer choice behavior among the products, and allows the products to use multiple units of a resource, while still maintaining the performance guarantee. In our computational experiments, we demonstrate that our approximate policy performs quite well, providing total expected revenues that are substantially better than its theoretical performance guarantee.